A free-form surface is employed in various industrial products, such as a ship, an automobile, and an airplane, and it offers an excellent compromise between functionality and aesthetic merit. Such free-form surface is used in designing appearances, or the like, of home electric appliances and many kinds of consumer products, having an aesthetic shape.
In recent years, a 3D laser scanner allows a high-speed and easy collection of high-density point group data, enabling a highly precise measurement of an object shape. By way of example, in the field of 3D modeling, there is employed a method, so-called “reverse engineering”, in which a designer manually creates a mockup model, uses the 3D laser scanner to measure the design, and generates CAD data such as surface data which is necessary for manufacturing a product, based on the point group data and polygon data captured into a computer.
In general, a polygon model or a surface patch such as NURBS and B-Spline represents the 3D model on the computer.
The polygon model is efficient in performing a shape processing such as a topological change. However, since the polygon model is made up of plain surfaces, it is not possible to represent a smooth surface, and there is another problem that if the shape is depicted in more detailed manner, enormous volumes of data are necessary.
As for the surface patch, it is possible to represent a smooth surface by the use of control parameters. However, there are problems that a shape of patch is limited to a quadrilateral, and in addition, it is difficult to maintain continuity between patches. In view of such problems, attention is being given to a subdivision method, as an effective method for a free-form shape modeling, which combines advantages of both the polygon model and the surface patch. This method has already been utilized in the field of animation commonly.
The subdivision method is a method which iteratively subjects an initial polygon mesh to a regular subdivision, thereby making the shape smoother, and ultimately obtaining a smooth surface. This surface is referred to a subdivision surface or a limit surface. The subdivision method has another feature that is able to generate a smooth surface easily even for a model in arbitrary topology. Furthermore, the surface can be defined smoothly in any part, and therefore this method is widely used in modeling, or the like.
In the field of reverse engineering, conventionally, there has been suggested a method for generating a surface by approximating or interpolating point group data which are measured by using the subdivision surfaces. The conventionally suggested method for interpolating the point group data by using the subdivision surfaces performs an operation processing for obtaining control points sequentially, so that a distance error between the initial control point obtained from the point group data and the surface being generated is minimized. The operation processing for obtaining the control point is performed by solving a linear matrix equation expressed by AP=S, where S represents a column of the point group, P represents a column of control points for generating the surface that approximates the point group, and A represents a basis function matrix that defines the surface.
As a conventionally suggested interpolation method, for example, there is known a method for interpolating a polyhedral mesh using Catmull-Clark subdivision surfaces, the method being suggested by Halsted, et al. (Non-patent document 1). The method needs to solve not only a large linear system, but also a minimization problem for surface adjustment, referred to as fairing, resulting in increase of computational cost.
In addition, Hoppe et al. suggests a method for approximating the group point data using Loop subdivision surface. This method assumes a polygon mesh having been subjected to the subdivision operation as subdivision surfaces linearly approximated, and the surfaces are further subjected to an orthogonal projection from each vertex for parameterization. Then, the method suggests handling the case as a least squares problem, aiming at obtaining a minimum distance between each vertex and an associated point on the subdivision surfaces being linearly approximated (Non-patent document 2).    Non-patent document 1: M. Halsted. M. Kass, and T. DeRose. Efficient, fair interpolation using Catmull-Clark surfaces. In Eugene Fiume, editor. In Proceedings of SIGGRAPH 1993, pages 47-61. ACM, ACM Press/ACM SIGGRAPH, 1993    Non-patent document 2: H. Hoppe, T. DeRpse. T. Duchamp, and M. Halsted. Piecewise smooth surface reconstruction. In Proceedings of SIGGRAPH 1994, pages 47-61, ACM, ACM Press/ACM SIGGRAPH, 1994    Non-patent document 3: C. T. Loop. Smooth subdivision surface based on triangle. Masters thesis, Department of Mathematics. University of Uta. 1987/.    Non-patent document 4: E. Catmull and J. Clark. Recursively generated b-spline surfaces on arbitrary topological meshes. Computer-Aided Design, 10(6): 350-355, 1987.    Non-patent document 5: D. Doo and M. Sabin. Behavior of recursive division surfaces near extraordinary points. Computer-Aided Design, 10(6): 356-360, 1978.    Non-patent document 6: G. M. Chaikin. An algorithm for high-speed curve generation. Computer Graphics and Image Processing, 3: 346-349, 1974.    Non-patent document 7: J. Stam. Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values. In Proceedings of SIGGRAPH on 1998, pages 395-404. AVM, ACM Press/ACM SIGGRAPH, 1998.    Non-patent document 8: M. Marinov and L. Kobbelt, Optimization methods for scattered data approximation with subdivision surface, Graphical Models 67, 2005, 452-473.    Non-patent document 9: R. P. Brent. Algorithms for Minimization without Derivatives. Prentice-Hall, Englewood Cliffs, N.J., 1986. 4.